Dijkstra's algorithm
Dijkstra's algorithm is one of the most widely used methods for finding single-source shortest paths in a simple digraph. In other words, Dijkstra's algorithm determines the shortest paths from a common vertex s to all other vertices in a digraph, if they exist. Algorithm Let G = (V,A) be a simple digraph with a function w(a) : A \to {\mathbb{R}}^{+} which assigns a weight, a non-negative real number, to each arc in G . Fix a source vertex s in G , from which shortest paths will be found. Additionally, for the purposes of the search itself, let d(v) denote the length of the shortest path from s to v . Let S denote the set of visited vertices, i.e., those vertices that have already been examined by the algorithm. Given a path \pi in G determined by the algorithm, let p(v) denote the predecessor of v for any v in \pi such that v \ne s . The meanings of these additions will become clear in the description of the algorithm. The execution proceeds as follows. Initial Stage #Let d(s) = 0 ....since there is no effort in staying in place. #For each vertex v adjacent from s , let d(v) be w((s,v)) , and let p(v) = s . #For each vertex v such that v \ne s and v is not adjacent from s , let d(v) = \infty .That is, the distance is unknown and v is assumed to be unreachable until it is proven otherwise. #Let S = \{s\} ....since no paths from s to itself need to be considered. Iterative Stage #Determine the vertex v that minimizes d(v) in V \setminus S , i.e., an unvisited vertex. #For each vertex u adjacent from v , compare the current value d(u) and n = d(v) + w((v,u)) . If n is the least of the two, let d(u) = n , and let p(u) = v . #Mark v as visited. That is, let S = S \cup \{v\} . #If S = V , all vertices have been visited; halt. Otherwise, return to the first step. Additional Details Interpretation of Results When the execution terminates, every vertex v for which d(v) < \infty has a shortest path. This shortest path is determined by repeated application of p(v) to v . For instance, a shortest path from s to v , four vertices long, would be described (s,p(p(v)),p(v),v) . For any vertex v where d(v) = \infty , there is, of course, no shortest path from s to v . Non-negativity Constraint Because Dijkstra's algorithm is a special case of uniform cost search, where there is no particular goal state, it is essential that w(a) \ge 0 for all arcs in G . Dynamic Programming Dijkstra's algorithm is also an instance of dynamic programming.To preempt any accusations of plagiarism, the description that follows was cribbed by the author from an article he himself wrote on PlanetMath. Let S_i equal the value of S in the i th iteration of the algorithm, where i=0 initially and S_0 = \{s\} . Let d(v,S_i) denote the weight of the shortest path from s to v , given the knowledge of S_i . Then w(v,S_i) = \begin{cases} 0 & \text{for $v = s$} \\ \min\{w((u,v)) + d(u, S_i)\} & \text{for $v \neq s$, where $v$ is adjacent from $u \in S_i$} \\ \infty & \text{otherwise} \end{cases} Therefore, the purpose of Dijkstra's algorithm is to determine the best policy for transforming the state of the problem (i.e., which vertex to move to next). It does so by refining an approximation of the best shortest-path policy for all vertices with each iteration, until the full solution is realized. The algorithm is efficient in practice because each iteration relies on previously determined information. Notes Category:Algorithms Category:Graph theory